{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Greater Multiple Made of Two Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findInteger"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小的仅由两个数组成的倍数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你三个整数, <code>k</code>, <code>digit1</code>和&nbsp;<code>digit2</code>, 你想要找到满足以下条件的 <strong>最小 </strong>整数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><span style=\"\"><b>大于</b></span><code>k</code> 且是 <code>k</code> 的<strong>倍数</strong></li>\n",
    "\t<li><strong>仅由</strong><code>digit1</code> <span style=\"\">和 </span><code>digit2</code> 组成，即 <strong>每一位数 </strong>均是 <code>digit1</code> 或 <code>digit2</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回<strong> </strong><strong>最小的满足这两个条件的整数</strong>，如果不存在这样的整数，或者最小的满足这两个条件的整数不在32位整数范围（0~<code>2<sup>31</sup>-1</code>），就返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 2, digit1 = 0, digit2 = 2\n",
    "<strong>输出：</strong>20\n",
    "<strong>解释：</strong>\n",
    "20 是第一个仅有数字0和2组成的，比2大且是2的倍数的整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 3, digit1 = 4, digit2 = 2\n",
    "<strong>输出：</strong>24\n",
    "<strong>解释：</strong>\n",
    "24 是第一个仅有数字 2 和 4 组成的，比 3 大且是 3 的倍数的整数。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 2, digit1 = 0, digit2 = 0\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：\n",
    "</strong>不存在仅由 0 组成的比 2 大且是 2 的倍数的整数，因此返回 -1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= digit1 &lt;= 9</code></li>\n",
    "\t<li><code>0 &lt;= digit2 &lt;= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-greater-multiple-made-of-two-digits](https://leetcode.cn/problems/smallest-greater-multiple-made-of-two-digits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-greater-multiple-made-of-two-digits](https://leetcode.cn/problems/smallest-greater-multiple-made-of-two-digits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n0\\n2', '3\\n4\\n2', '2\\n0\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findInteger(self, k: int, digit1: int, digit2: int) -> int:\n",
    "        MAX = 2 ** 31\n",
    "        if not digit1 and not digit2:\n",
    "            return -1\n",
    "        q = [digit1, digit2]\n",
    "        ans = inf\n",
    "        for i in range(11):\n",
    "            nq = []\n",
    "            for x in q:\n",
    "                if x > k and x % k == 0:\n",
    "                    ans = min(ans, x)\n",
    "                res = x * 10 + digit1\n",
    "                if res < MAX:\n",
    "                    nq.append(res)\n",
    "                res = x * 10 + digit2\n",
    "                if res < MAX:\n",
    "                    nq.append(res)\n",
    "            if ans < inf:\n",
    "                return ans\n",
    "            q = nq\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # bfs\n",
    "    # 按顺序搜索，搜到第一个有效结果就返回\n",
    "    def findInteger(self, k: int, digit1: int, digit2: int) -> int:\n",
    "        if digit1 == 0 and digit2 == 0:\n",
    "            return -1\n",
    "\n",
    "        if digit1 > digit2:\n",
    "            digit1, digit2 = digit2, digit1\n",
    "\n",
    "        queue = deque([digit1, digit2])\n",
    "\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            if cur > (2 ** 31 - 1):\n",
    "                return -1\n",
    "                \n",
    "            if cur % k == 0 and cur > k:\n",
    "                return cur\n",
    "\n",
    "            # 按照顺序加入队列 整个队列都是有序的\n",
    "            queue.append(cur * 10 + digit1)\n",
    "            queue.append(cur * 10 + digit2)\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findInteger(self, k: int, digit1: int, digit2: int) -> int:\n",
    "        L = sorted(set([digit1, digit2]))\n",
    "        if L[-1] == 0:\n",
    "            return -1\n",
    "        dq = deque(L)\n",
    "        while dq:\n",
    "            a = dq.popleft()\n",
    "            if a > 2 ** 31 - 1:\n",
    "                return -1\n",
    "            if a % k == 0 and a > k:\n",
    "                return a \n",
    "            dq.append(10 * a + L[0])\n",
    "            dq.append(10 * a + L[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findInteger(self, k: int, digit1: int, digit2: int) -> int:\n",
    "        ans=[inf]\n",
    "        def dfs(x):\n",
    "            if x==0 or x>=(1<<31)-1:\n",
    "                return \n",
    "            if x>k and x%k==0:\n",
    "                ans[0]=min(ans[0],x)\n",
    "                return \n",
    "            dfs(x*10+digit1)\n",
    "            dfs(x*10+digit2)\n",
    "        dfs(digit1)\n",
    "        dfs(digit2)\n",
    "        return ans[0] if ans[0]!=inf else -1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findInteger(self, k: int, digit1: int, digit2: int) -> int:\n",
    "        mx = 2 ** 31 - 1\n",
    "        chosen = sorted(set([digit1, digit2]))\n",
    "        canbe_first = set(chosen) - {0}\n",
    "        canbe_first = sorted(canbe_first)\n",
    "        if not canbe_first:\n",
    "            return -1\n",
    "        for i in canbe_first:\n",
    "            if i % k == 0 and i > k:\n",
    "                return i \n",
    "        tmp = []\n",
    "        for i in canbe_first:\n",
    "            for j in chosen:\n",
    "                a = 10 * i + j \n",
    "                if a % k == 0 and a > k:\n",
    "                    return a \n",
    "                tmp.append(a)\n",
    "        overflow = False\n",
    "        for _ in range(100):\n",
    "            if overflow:\n",
    "                break \n",
    "            res = []\n",
    "            for i in tmp:\n",
    "                if overflow:\n",
    "                    break \n",
    "                for j in chosen:\n",
    "                    a = i * 10 + j \n",
    "                    if a > mx:\n",
    "                        overflow = True\n",
    "                        break\n",
    "                    if a % k == 0 and a > k:\n",
    "                        return a \n",
    "                    res.append(a)\n",
    "            tmp = res[::]\n",
    "        return -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findInteger(self, k: int, digit1: int, digit2: int) -> int:\n",
    "        ans = inf\n",
    "        def f(x):\n",
    "            nonlocal ans\n",
    "            y = int(x)\n",
    "            if len(x) > 10: return\n",
    "            if y > 2 ** 31 - 1: return\n",
    "            if y % k == 0 and y > k:\n",
    "                ans = min(ans, y)\n",
    "            f(x+str(digit1))\n",
    "            f(x+str(digit2))\n",
    "        f(str(digit1))\n",
    "        f(str(digit2))\n",
    "        return -1 if ans == inf else ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
